/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cuatroenraya.jugadores;

import java.util.*;
import cuatroenraya.Jugador;

/**
 *
 * @author Gonzalo
 */
public class JugadorAlumnoG03 extends Jugador
{
    private int cantidadJugadas;
    private int numeroNodo;
    private int[] ultimaUbicacionPropia = new int[2];

    //Constructor de la clase JugadorGNN
    public JugadorAlumnoG03(int cantF)
    {
        super(cantF);
        super.nombre = "Grupo NN2";
        super.numeroJugador = 1;
        this.cantidadJugadas = 0;
    }

    public String getNombre() {
        return nombre;
    }

    public void setNombre(String nombre) {
        this.nombre = nombre;
    }

    public int getNumeroJugador() {
        return numeroJugador;
    }

    public void setNumeroJugador(int numeroJugador) {
        this.numeroJugador = numeroJugador;
    }

    @Override
    //Método que determina la jugada a realizar
    public int[] jugar(int[][] tablero)
    {
        if(cantidadJugadas < this.cantFichas)
        {
            return JugadaSinMovimiento(tablero);
        }
        else
        {
            return JugadaConMovimiento(tablero);
        }
    }

    private int[] JugadaConMovimiento(int[][] tablero)
    {
        this.numeroNodo = 0;
        HashSet cerrada = new HashSet(200);
        PriorityQueue<Estado> abierta = new PriorityQueue<Estado>(1500);
        
        Estado raiz = new Estado(this.numeroNodo, tablero, 0, 0, new int[4], null);
        abierta.add(raiz);
        this.numeroNodo++;
        Estado meta = null, mejorMovimiento = raiz;
        while(!abierta.isEmpty() && meta == null)
        {
            Estado m = (Estado)abierta.poll();
            cerrada.add(m);
            //Comprobamos la profundidad de la búsqueda, límite = 5
            //if(m.distanciaRaiz < 5) { estados = ExpandirEstado(m, abierta, cerrada); }
            List<Estado> estados = ExpandirEstado(m, abierta, cerrada);
            Iterator iterador = estados.iterator();
            while(iterador.hasNext())
            {
                //Vemos si es jugada ganadora para terminar la búsqueda
                Estado estado = (Estado)iterador.next();
                if(EsJugadaGanadora(estado))
                { meta = estado; }
                else
                {
                    abierta.add(estado);
                    //Guardamos el mejor movimiento en base a la heurística
                    if(mejorMovimiento != null && estado.distanciaRaiz == 1 && estado.valorHeuristico > mejorMovimiento.valorHeuristico)
                    { mejorMovimiento = estado; }
                }
            }
        }

        if(meta == null)
        {
            //No encontró una solución, gran problema, devolvemos el mejor movimiento guardado
            return mejorMovimiento.movimiento;
        }

        //Volvemos hasta el primer movimiento desde la raíz
        while(meta.distanciaRaiz > 1)
        {
            meta = meta.padre;
        }
        
        return meta.movimiento;
    }

    private int[] JugadaSinMovimiento(int[][] tablero)
    {
        int[] jugada = new int[4];

        if(this.cantidadJugadas == 0)
        {
            //No hemos colocado ninguna ficha, seleccionemos un lugar medio
            int ubicacion;
            if(tablero[3][3] == 0) { ubicacion = 3;}
            else { ubicacion = 4; }
            jugada[2] = ubicacion;
            jugada[3] = ubicacion;
        }
        else
        {
            //Ya colocamos una ficha, primero vemos el estado del rival
            //Si tiene dos en línea sin bloquear entonces lo bloqueamos
            boolean jugadaEncontrada = false;
            int[][] fichasPropias = new int[this.cantFichas][2];
            int[][] fichasRival = new int[this.cantFichas][2];
            EncontrarFichas(tablero, fichasPropias, fichasRival);
            int[] ubicacion = new int[4];
            for(int i = 0; i < this.cantFichas; i++)
            {
                ubicacion[2] = fichasRival[i][0];
                ubicacion[3] = fichasRival[i][1];
                if(EsDosEnLineaSinBloquear(tablero, ubicacion, 2))
                {
                    jugada[2] = ubicacion[0];
                    jugada[3] = ubicacion[1];
                    jugadaEncontrada = true;
                    i = this.cantFichas;
                }
            }

            if(!jugadaEncontrada)
            {
                //Usemos la heurística para la siguiente ubicación
                double ultimaHeuristica = 0, heuristicaTemp = 0;
                for(int fila = ultimaUbicacionPropia[0]-1; fila <= ultimaUbicacionPropia[0]+1; fila++)
                {
                    for(int columna = ultimaUbicacionPropia[1]-1; columna <= ultimaUbicacionPropia[1]+1; columna++)
                    {
                        //Comprobamos si la posición está dentro del tablero
                        if(fila >= 0 && fila < 8 && columna >= 0 && columna < 8)
                        {
                            //Comprobamos si la posición del tablero está vacia
                            if(tablero[fila][columna] == 0)
                            {
                                int[] temp = new int[4];
                                temp[2] = fila;
                                temp[3] = columna;
                                heuristicaTemp = CalcularHeuristica(tablero, temp);
                                if(heuristicaTemp > ultimaHeuristica)
                                {
                                    ultimaHeuristica = heuristicaTemp;
                                    jugada[2] = temp[2];
                                    jugada[3] = temp[3];
                                }
                            }
                        }
                    }
                }
            }
        }
        ultimaUbicacionPropia[0] = jugada[2];
        ultimaUbicacionPropia[1] = jugada[3];
        this.cantidadJugadas++;
        return jugada;
    }

    private List<Estado> ExpandirEstado(Estado estado, PriorityQueue<Estado> abierta, HashSet cerrada)
    {
        //Lista que almacena los nuevos estados generados a devolver
        List<Estado> listaEstados = new ArrayList<Estado>();
        //Recorremos el tablero del nodo actual, i filas, j columnas
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                //Si encontramos una ficha nuestra creamos los estados para cada movimiento posible
                if(estado.estadoTablero[i][j] == this.numeroJugador)
                {
                    //Recorremos los 8-vecinos de la ficha encontrada
                    for(int fila = i-1; fila <= i+1; fila++)
                    {
                        for(int columna = j-1; columna < j+1; columna++)
                        {
                            //Comprobamos si la posición está dentro del tablero
                            if(fila >= 0 && fila < 8 && columna >= 0 && columna < 8)
                            {
                                //Comprobamos si la posición del tablero está vacia
                                if(estado.estadoTablero[fila][columna] == 0)
                                {
                                    //Espacio vacio, creamos el nuevo nodo
                                    int[] movimiento = new int[4];
                                    movimiento[0] = i;
                                    movimiento[1] = j;
                                    movimiento[2] = fila;
                                    movimiento[3] = columna;
                                    int[][] tableroParametro = TableroParametro(estado.getEstadoTablero());
                                    tableroParametro[i][j] = 0;
                                    tableroParametro[fila][columna] = this.numeroJugador;
                                    Estado nuevoEstado = new Estado(numeroNodo, tableroParametro, CalcularHeuristica(tableroParametro, movimiento) - (estado.distanciaRaiz + 1), estado.distanciaRaiz + 1, movimiento, estado);

                                    //Lo agregamos a la lista de estados si no lo hemos generado o procesado antes
                                    if(!abierta.contains(nuevoEstado) && !cerrada.contains(nuevoEstado))
                                    {
                                        //Controlamos si el estado nuevo es jugada ganadora, en tal caso devolvemos
                                        //sólo ese estado y cortamos todo el proceso
                                        if(EsJugadaGanadora(nuevoEstado))
                                        {
                                            listaEstados.clear();
                                            listaEstados.add(nuevoEstado);
                                            return listaEstados;
                                        }
                                        listaEstados.add(nuevoEstado);
                                        numeroNodo++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        return listaEstados;
    }

    private double CalcularHeuristica(int[][] tablero, int[] movimiento)
    {
        double verticalS = 0, verticalI = 0, horizontalI = 0, horizontalD = 0, diagonal0 = 0, diagonal2 = 0;
        double diagonal4 = 0, diagonal6 = 0, grupo = 0, valorVacio = 0.1;
        int distanciaCentro = 0, distanciaEntreFichas = 0, fila = 0, columna = 0;

        //Buscamos el centro de gravedad
        for(int i = 1; i < 9; i++)
        {
            int acumuladoFila = 0, acumuladoColumna = 0;
            for(int j = 1; j < 9; j++)
            {
                if(tablero[i-1][j-1] == this.numeroJugador) { acumuladoFila++; }
                if(tablero[j-1][i-1] == this.numeroJugador) { acumuladoColumna++; }
            }
            fila += acumuladoFila * i;
            columna += acumuladoColumna * i;
        }
        fila = Math.round(fila * Float.parseFloat("0.2")) - 1;
        columna = Math.round(columna * Float.parseFloat("0.2")) - 1;

        //Determina un valor en base a la cantidad de fichas cercanas del movimiento que den una línea
        //al mismo tiempo asigna un valor a un espacio vacio con una ficha propia cercanas
        for(int i = 1; i < 4;  i++)
        {
            //Diagonal 0
            int f = movimiento[2]-i;
            int c = movimiento[3]-i;
            if(f >= 0 && c >= 0)
            {
                if(tablero[f][c] == this.numeroJugador) { diagonal0++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c-1 > 0 && tablero[f+1][c-1] == this.numeroJugador) { fichas++; }
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    diagonal0+= fichas * valorVacio;
                }
            }

            //Diagonal 2
            f = movimiento[2]-i;
            c = movimiento[3]+i;
            if(f >= 0 && c < 8)
            {
                if(tablero[f][c] == this.numeroJugador) { diagonal2++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    diagonal2 += fichas * valorVacio;
                }
            }

            //Diagonal 4
            f = movimiento[2]+i;
            c = movimiento[3]+i;
            if(f < 8 && c < 8)
            {
                if(tablero[f][c] == this.numeroJugador) { diagonal4++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c-1 >= 0 && tablero[f+1][c-1] == this.numeroJugador) { fichas++; }
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    diagonal4 += fichas * valorVacio;
                }
            }

            //Diagonal 6
            f = movimiento[2]+i;
            c = movimiento[3]-i;
            if(f < 8 && c >= 0)
            {
                if(tablero[f][c] == this.numeroJugador) { diagonal6++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    diagonal6 += fichas * valorVacio;
                }
            }

            //Vertical superior
            f = movimiento[2]-i;
            c = movimiento[3];
            if(f >= 0)
            {
                if(tablero[f][c] == this.numeroJugador) { verticalS++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c-1 >= 0 && tablero[f+1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    verticalS += fichas * valorVacio;
                }
            }

            //Vertical inferior
            f = movimiento[2]+i;
            c = movimiento[3];
            if(f < 8)
            {
                if(tablero[f][c] == this.numeroJugador) { verticalI++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(c-1 >= 0 && tablero[f][c-1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c-1 >= 0 && tablero[f+1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(c+1 < 8 && tablero[f][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    verticalI += fichas * valorVacio;
                }
            }

            //Horizontal izquierda
            f = movimiento[2];
            c = movimiento[3]-i;
            if(c >= 0)
            {
                if(tablero[f][c] == this.numeroJugador) { horizontalI++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    horizontalI += fichas * valorVacio;
                }
            }

            //Horizontal derecha
            f = movimiento[2];
            c = movimiento[3]+i;
            if(c < 8)
            {
                if(tablero[f][c] == this.numeroJugador) { horizontalD++; }
                else if(tablero[f][c] == 0)
                {
                    double fichas = 0;
                    if(f-1 >= 0 && c-1 >= 0 && tablero[f-1][c-1] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && tablero[f-1][c] == this.numeroJugador) { fichas++; }
                    if(f-1 >= 0 && c+1 < 8 && tablero[f-1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && tablero[f+1][c] == this.numeroJugador) { fichas++; }
                    if(f+1 < 8 && c+1 < 8 && tablero[f+1][c+1] == this.numeroJugador) { fichas++; }
                    horizontalD += fichas * valorVacio;
                }
            }
        }

        grupo = verticalS + verticalI + horizontalI + horizontalD + diagonal0 + diagonal2 + diagonal4 + diagonal6;

        //Calcula la distancia D8 del movimiento al centro de gravedad
        int x = movimiento[2] - fila;
        int y = movimiento[3] - columna;
        distanciaCentro = 0;//(Math.abs(x) > Math.abs(y)) ? Math.abs(x) : Math.abs(y);

        //Calcula la distancia D8 entre fichas para evitar el problema de no encontrar
        //solución, o tardar demasiado, si están muy dispersas
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                if(tablero[i][j] == this.numeroJugador)
                {
                    x = movimiento[2] - i;
                    y = movimiento[3] - j;
                    distanciaEntreFichas += (Math.abs(x) > Math.abs(y)) ? Math.abs(x) : Math.abs(y);
                }
            }
        }

        if(this.cantidadJugadas < this.cantFichas || grupo > 2) return grupo;
        return grupo - distanciaCentro - distanciaEntreFichas;
    }

    private boolean EsJugadaGanadora(Estado estado)
    {
        int vertical = 0;
        int horizontal = 0;
        int diagonal04 = 0;
        int diagonal26 = 0;
        int[][] tablero = estado.getEstadoTablero();
        int[] jugada = estado.getMovimiento();

        for(int i = -3; i < 4;  i++)
        {
            if(jugada[2]+i >= 0 && jugada[2]+i < 8)
            {
                if(tablero[jugada[2]+i][jugada[3]] == this.numeroJugador) { vertical++; }
                else { vertical = 0; }
            }

            if(jugada[3]+i >= 0 && jugada[3]+i < 8)
            {
                if(tablero[jugada[2]][jugada[3]+i] == this.numeroJugador) { horizontal++; }
                else { horizontal = 0; }
            }

            if(jugada[2]+i < 8 && jugada[2]+i >= 0 && jugada[3]+i < 8 && jugada[3]+i >=0)
            {
                if(tablero[jugada[2]+i][jugada[3]+i] == this.numeroJugador) { diagonal04++; }
                else { diagonal04 = 0; }
            }

            if(jugada[2]+i < 8 && jugada[2]+i >= 0 && jugada[3]-i < 8 && jugada[3]-i >=0)
            {
                if(tablero[jugada[2]+i][jugada[3]-i] == this.numeroJugador) { diagonal26++; }
                else { diagonal26 = 0; }
            }

            if(vertical == 4 || horizontal == 4 || diagonal04 == 4 || diagonal26 == 4)
            {
                return true;
            }
        }
        return false;
    }

    private boolean EsDosEnLineaSinBloquear(int[][] tablero, int[] ubicacion, int numeroFicha)
    {
        int vertical = 0;
        int horizontal = 0;
        int diagonal04 = 0;
        int diagonal26 = 0;

        for(int i = -3; i < 4;  i++)
        {
            if(ubicacion[2]+i >= 0 && ubicacion[2]+i < 8)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]] == numeroFicha) { vertical++; }
                else { vertical = 0; }
            }

            if(ubicacion[3]+i >= 0 && ubicacion[3]+i < 8)
            {
                if(tablero[ubicacion[2]][ubicacion[3]+i] == numeroFicha) { horizontal++; }
                else { horizontal = 0; }
            }

            if(ubicacion[2]+i < 8 && ubicacion[2]+i >= 0 && ubicacion[3]+i < 8 && ubicacion[3]+i >=0)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]+i] == numeroFicha) { diagonal04++; }
                else { diagonal04 = 0; }
            }

            if(ubicacion[2]+i < 8 && ubicacion[2]+i >= 0 && ubicacion[3]-i < 8 && ubicacion[3]-i >=0)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]-i] == numeroFicha) { diagonal26++; }
                else { diagonal26 = 0; }
            }

            if(vertical == 2)
            {
                if(ubicacion[2]-1 >= 0 && tablero[ubicacion[2]-1][ubicacion[3]] == numeroFicha)
                {
                    if((ubicacion[2]-2 >=0 && tablero[ubicacion[2]-2][ubicacion[3]] == 0) || (ubicacion[2]+1 < 8 && tablero[ubicacion[2]+1][ubicacion[3]] == 0))
                    {
                        ubicacion[0] = (ubicacion[2]-2 >=0) ? (ubicacion[2]-2): (ubicacion[2]+1);
                        ubicacion[1] = ubicacion[3];
                        return true;
                    }
                }
                else
                {
                    if((ubicacion[2]-1 >=0 && tablero[ubicacion[2]-1][ubicacion[3]] == 0) || (ubicacion[2]+2 < 8 && tablero[ubicacion[2]+2][ubicacion[3]] == 0))
                    {
                        ubicacion[0] = (ubicacion[2]-1 >=0) ? (ubicacion[2]-1): (ubicacion[2]+2);
                        ubicacion[1] = ubicacion[3];
                        return true;
                    }
                }                
            }

            if(horizontal == 2)
            {
                if(ubicacion[3]-1 >= 0 && tablero[ubicacion[2]][ubicacion[3]-1] == numeroFicha)
                {
                    if((ubicacion[3]-2 >=0 && tablero[ubicacion[2]][ubicacion[3]-2] == 0) || (ubicacion[3]+1 < 8 && tablero[ubicacion[2]][ubicacion[3]+1] == 0))
                    {
                        ubicacion[0] = ubicacion[2];
                        ubicacion[1] = (ubicacion[3]-2 >=0) ? (ubicacion[3]-2): (ubicacion[3]+1);
                        return true;
                    }
                }
                else
                {
                    if((ubicacion[3]-1 >=0 && tablero[ubicacion[2]][ubicacion[3]-1] == 0) || (ubicacion[3]+2 < 8 && tablero[ubicacion[2]][ubicacion[3]+2] == 0))
                    {
                        ubicacion[0] = ubicacion[2];
                        ubicacion[1] = (ubicacion[3]-1 >=0) ? (ubicacion[3]-1): (ubicacion[3]+2);
                        return true;
                    }
                }
            }

            if(diagonal04 == 2)
            {
                if(ubicacion[2]-1 >= 0 && ubicacion[3]-1 >= 0 && tablero[ubicacion[2]-1][ubicacion[3]-1] == numeroFicha)
                {
                    if((ubicacion[2]-2 >= 0 && ubicacion[3]-2 >= 0 && tablero[ubicacion[2]-2][ubicacion[3]-2] == 0) || (ubicacion[2]+1 < 8 && ubicacion[3]+1 < 8 && tablero[ubicacion[2]+1][ubicacion[3]+1] == 0))
                    {
                        if(ubicacion[2]-2 >= 0 && ubicacion[3]-2 >= 0)
                        {
                            ubicacion[0] = ubicacion[2]-2;
                            ubicacion[1] = ubicacion[3]-2;
                        }
                        else
                        {
                            ubicacion[0] = ubicacion[2]+1;
                            ubicacion[1] = ubicacion[3]+1;
                        }
                        return true;
                    }
                }
                else
                {
                    if((ubicacion[2]+2 < 8 && ubicacion[3]+2 < 8 && tablero[ubicacion[2]+2][ubicacion[3]+2] == 0) || (ubicacion[2]-1 >= 0 && ubicacion[3]-1 >= 0 && tablero[ubicacion[2]-1][ubicacion[3]-1] == 0))
                    {
                        if(ubicacion[2]+2 < 8 && ubicacion[3]+2 < 8)
                        {
                            ubicacion[0] = ubicacion[2]+2;
                            ubicacion[1] = ubicacion[3]+2;
                        }
                        else
                        {
                            ubicacion[0] = ubicacion[2]-1;
                            ubicacion[1] = ubicacion[3]-1;
                        }
                        return true;
                    }
                }
            }

            if(diagonal26 == 2)
            {
                if(ubicacion[2]-1 >= 0 && ubicacion[3]+1 < 8 && tablero[ubicacion[2]-1][ubicacion[3]+1] == numeroFicha)
                {
                    if((ubicacion[2]-2 >= 0 && ubicacion[3]+2 < 8 && tablero[ubicacion[2]-2][ubicacion[3]+2] == 0) || (ubicacion[2]+1 < 8 && ubicacion[3]-1 >= 0 && tablero[ubicacion[2]+1][ubicacion[3]-1] == 0))
                    {
                        if(ubicacion[2]-2 >= 0 && ubicacion[3]+2 < 8)
                        {
                            ubicacion[0] = ubicacion[2]-2;
                            ubicacion[1] = ubicacion[3]+2;
                        }
                        else
                        {
                            ubicacion[0] = ubicacion[2]+1;
                            ubicacion[1] = ubicacion[3]-1;
                        }
                        return true;
                    }
                }
                else
                {
                    if((ubicacion[2]+2 < 8 && ubicacion[3]-2 >= 0 && tablero[ubicacion[2]+2][ubicacion[3]-2] == 0) || (ubicacion[2]-1 >= 0 && ubicacion[3]+1 < 8 && tablero[ubicacion[2]-1][ubicacion[3]+1] == 0))
                    {
                        if(ubicacion[2]+2 < 8 && ubicacion[3]+2 < 8)
                        {
                            ubicacion[0] = ubicacion[2]+2;
                            ubicacion[1] = ubicacion[3]-2;
                        }
                        else
                        {
                            ubicacion[0] = ubicacion[2]-1;
                            ubicacion[1] = ubicacion[3]+1;
                        }
                        return true;
                    }
                }
            }
            
        }
        return false;
    }

    private int EsTresEnLinea(int[][] tablero, int[] ubicacion, int numeroFicha)
    {
        int vertical = 0;
        int horizontal = 0;
        int diagonal04 = 0;
        int diagonal26 = 0;

        for(int i = -3; i < 4;  i++)
        {
            if(ubicacion[2]+i >= 0 && ubicacion[2]+i < 8)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]] == numeroFicha) { vertical++; }
                else { vertical = 0; }
            }

            if(ubicacion[3]+i >= 0 && ubicacion[3]+i < 8)
            {
                if(tablero[ubicacion[2]][ubicacion[3]+i] == numeroFicha) { horizontal++; }
                else { horizontal = 0; }
            }

            if(ubicacion[2]+i < 8 && ubicacion[2]+i >= 0 && ubicacion[3]+i < 8 && ubicacion[3]+i >=0)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]+i] == numeroFicha) { diagonal04++; }
                else { diagonal04 = 0; }
            }

            if(ubicacion[2]+i < 8 && ubicacion[2]+i >= 0 && ubicacion[3]-i < 8 && ubicacion[3]-i >=0)
            {
                if(tablero[ubicacion[2]+i][ubicacion[3]-i] == numeroFicha) { diagonal26++; }
                else { diagonal26 = 0; }
            }

            if(diagonal04 == 3) {return 0;}
            if(vertical == 3) { return 1; }
            if(diagonal26 == 3) { return 2; }
            if(horizontal == 3) { return 3; }
        }
        return -1;
    }

    private int[][] TableroParametro(int[][] tablero)
    {
        int[][] tableroParametro = new int[8][8];
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                tableroParametro[i][j] = tablero[i][j];
            }
        }

        return tableroParametro;
    }

    private void EncontrarFichas(int[][] tablero, int[][] fichasPropias, int[][] fichasRival)
    {
        int cantidadFichasPropias = 0, cantidadFichasRival = 0;
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                if(tablero[i][j] != this.numeroJugador && tablero[i][j] != 0)
                {
                    fichasRival[cantidadFichasRival][0] = i;
                    fichasRival[cantidadFichasRival][1] = j;
                    cantidadFichasRival++;
                }
                if(tablero[i][j] == this.numeroJugador)
                {
                    fichasPropias[cantidadFichasPropias][0] = i;
                    fichasPropias[cantidadFichasPropias][1] = j;
                    cantidadFichasPropias++;
                }

                if(cantidadFichasRival == this.cantFichas && cantidadFichasPropias == this.cantFichas) return;
            }
        }
    }

    //Clases internas para representar las listas, los nodos y los estados del tablero
    class Estado implements Comparable
    {
        public Estado(int numero, int[][] tablero, double valorHeuristica, int distanciaRaiz, int[] movimiento, Estado estadoPadre)
        {
            this.estadoTablero = tablero;
            this.valorHeuristico = valorHeuristica;
            this.numeroNodo = numero;
            this.distanciaRaiz = distanciaRaiz;
            this.movimiento = movimiento;
            this.padre = estadoPadre;
        }

        private int numeroNodo;
        private int[][] estadoTablero;
        private double valorHeuristico;
        private int distanciaRaiz;
        private int[] movimiento;
        private Estado padre;

        public int[][] getEstadoTablero() {
            return estadoTablero;
        }

        public double getValorHeuristico() {
            return valorHeuristico;
        }

        public int getDistanciaRaiz() {
            return distanciaRaiz;
        }

        public int getNumeroNodo() {
            return numeroNodo;
        }

        public int[] getMovimiento() {
            return movimiento;
        }

        public Estado getPadre() {
            return padre;
        }

        public void setPadre(Estado padre) {
            this.padre = padre;
        }

        public int compareTo(Object o) {
            Estado n = (Estado)o;
            double valor = this.valorHeuristico - n.valorHeuristico;
            if(valor > 0) return -1;
            if(valor < 0) return 1;
            if(this.distanciaRaiz < n.distanciaRaiz) return -1;
            if(this.distanciaRaiz > n.distanciaRaiz) return 1;
            return 0;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj instanceof Estado)
            {
                Estado n = (Estado)obj;
                for(int i = 0; i < 8; i++)
                {
                    for(int j = 0; j < 8; j++)
                    {
                        if(this.estadoTablero[i][j] != n.getEstadoTablero()[i][j]) return false;
                    }
                }
                return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 41 * hash + this.numeroNodo;
            return hash;
        }
    }
}
